package 单调栈;

import java.util.Stack;

public class 不同字符的最小子序列 {
    public String smallestSubsequence(String s) {
        Stack<Character> stack = new Stack<>();
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            char c = arr[i];
            if (stack.contains(c))
                continue;
            while (!stack.isEmpty() && s.indexOf(stack.peek(),i)!=-1 && stack.peek()>c)
                stack.pop();
            stack.push(c);
        }
        char[] chars = new char[stack.size()];
        for (int i = stack.size()-1; i >=0 ; i--) {
            chars[i]=stack.pop();
        }
        return new String(chars);
    }
}
